高德KDD2020论文解读|混合时空图卷积网络：更精准的时空预测模型

导读

时空预测在天气预报、运输规划等领域有着重要的应用价值。交通预测作为一种典型的时空预测问题，具有较高的挑战性。以往的研究中主要利用通行时间这类交通状态特征作为模型输入，很难预测整体的交通状况，本文提出的混合时空图卷积网络，利用导航数据大大提升了时空预测的效果（本文作者高德机器学习团队，论文已被收录到KDD2020）。

论文下载地址：https://arxiv.org/abs/2006.12715

日常通勤中的规律往往相对容易挖掘，但交通状况还会受很多其他因素影响，之前的研究主要利用通行时间这类交通状态作为特征，少量研究引入事件，不能很好地预测实际交通流量。

为解决这一问题，本文从高德导航引擎中获取了「计划中交通流量」，并将其扩充到机器学习模型当中。

计划中交通流量来自导航数据，反映了用户出行意图中蕴含的未来交通流量。由于拥有海量用户，高德地图中的导航规划数据能够较为全面地反应正在发生的通行需求，并且信息粒度较事件级别的特征更精细。

具体来说，规划的路线产生了计划中交通流量，而计划中交通流量可以用来指导对未来通行时间的预测。volf代表当前可获取的导航路径在f个时间步后在此路段产生的计划中交通流量。计划中交通流量的迅速飙升意味着即将到来的交通拥堵。

图 1  北京某路段在2019年10月28日早高峰期间通行时间和计划中交通流量

为了将交通流量这一异质信号整合到通行时间预测模型当中，我们创新性地设计出一种域转换器（domain transformer）结构，用于将交通流量信息转化为通行时间信息。

交通流理论中，路段的交通流量和车辆密度呈三角形曲线映射关系，而曲线的参数是因路段而异的。图2展示了现实世界中的例子。为了利用这一转换关系，我们设计了将流量转化为通行时间的转换器，该转换器由两层网络构成，分别用于提取全局共享信息和学习不同路段的精细化信息。

图 2  四个不同路段的流量时间曲线

另一方面，由于交通网络的非欧几里得特性，我们利用图卷积（graph convolution）结构提取空间依赖性特征，并设计了一种新的邻接矩阵用于更好地体现路段间的交通邻近性。

在以往的研究中[6]，邻接矩阵的权重只按距离衰减，并没有考虑到路段间固有的交通邻近性（图 3 给出了距离近但交通状态相差较大的例子）。为解决这一问题，我们设计了一种复合邻接矩阵（compound adjacency matrix），在距离衰减的基础上进一步引入了路段通行时间的协方差。

图 3  相邻道路间拥堵不一定会传播

本文提出的混合时空图卷积网络（Hybrid Spatio-Temporal Graph Convolutional Network，H-STGCN）是综合利用上述技术的交通预测框架。

在H-STGCN中，转换器将未来交通流量信号转化为通行时间信号。路段间参数共享的门控卷积用于提取时间依赖信息。

基于复合邻接矩阵的图卷积从合并后的通行时间信号中捕捉空间依赖信息。H-STGCN经由端到端的训练，可具备基于计划中交通流量信息预测未来拥堵的能力。利用真实交通数据集进行实验可验证，H-STGCN的效果显著优于各种前沿模型。

混合时空图卷积网络，独创域转换器和复合邻接矩阵

整体框架

图 4 展示了H-STGCN的整体框架。模型输入由两个特征张量组成，理想未来流量和通行时间张量。和均包含三个维度：空间维度、时间维度、通道维度，分别对应路段、所使用的时间片和特征。

域转换器（模块a）首先将转化为通行时间信号，输出未来通行时间张量。接下来，两个独立的门控卷积（模块b）分别作用于和的时间维度以提取更高层级的时域特征。

将每个路段视为一个节点，基于复合邻接矩阵的图卷积（模块c）作用在合并（concatenation）后的信号上。两个门控卷积继续扩大时域上的感知范围，并最终经由一个全连接层（FC）输出预测结果。

图 4  H-STGCN模型框架   

模型输入与数据处理

输入特征张量的每个切片对应了一个单独的时间片 （）。每个切片又由两部分组成：理想未来流量和通行时间。

理想未来流量 。作为对真实未来流量这一无法获取信息的近似，理想未来流量可以通过在线导航引擎获取。图 5 示意了高德导航系统的架构。导航过程中，车辆每秒钟与云服务器同步自身坐标，与此同时，为保证用户获取到最新的交通状态信息，云服务器对ETA进行几乎实时的持续更新。

图 5  高德导航系统架构示意

高德导航引擎中原始数据的形式为

其中是导航进程的索引号，是导航的发起时间，代表规划路线中的第个路段，是到达的预估时间， 是路线中路段的总数量，是导航进程的总数量。ETA来自机器学习模型的预测（利用历史轨迹等数据训练得到）。算法 1 展示了从导航路线集合中推算理想未来流量的方法。

H-STGCN中，与预测时间窗口相对应的理想未来流量和历史平均流量同时被输入：

其中是路段的索引号。

通行时间 。通行时间通过完成地图匹配的GPS点数据整合计算得到。H-STGCN中，通行时间及其与预测时间窗口相对应的历史均值同时被用于模型的输入：

其中是路段的索引号。

域转换器

域转换器由串联的两层网络组成，即逐路段卷积（segmentwise  convolution）和路段间共享卷积（shared  convolution），图 4 呈现了这一结构。

图 6  H-STGCN中的各种卷积运算

共享卷积。路段及时间片间参数共享的卷积层位于域转换器的顶部，该卷积运算阐释如图 6a，旨在捕捉全局的三角形曲线映射关系。记这一层的输入和输出为与，则有：

其中为权重，为偏置项，为ELU（Exponential Linear Unit）激活函数。

逐路段卷积。为保证模型能够充分提取精细到路段级别的特征，路段参数个性化的卷积层位于域转换器的底部（共享卷积前面一层），该卷积运算阐释如图 6b。记这一层的输入和输出为与，则有：

其中，为权重，为偏置项，是ELU激活函数。

基于复合邻接矩阵的图卷积

复合邻接矩阵。以往研究[6,7]中的邻接矩阵假设节点间的接近性简单地依距离衰减：

其中为路段与的最短路距离，控制衰减速率，为控制矩阵稀疏性的截断阈值。我们将称为迪杰斯特拉矩阵（Dijkstra matrix）。在很多场景下，单纯的空间接近程度并不能反映真实的交通邻近性。更具体而言，交通拥堵对交通分流的影响取决于邻近路段的若干种属性，包括道路等级、路况等。可见，拥堵的传播在空间上并不均匀。由此，我们提出了复合邻接矩阵：

图卷积 。我们将交通路网视为一个以路段为节点的图。归一化图拉普拉斯（normalized graph Laplacian）矩阵和缩放变换的图拉普拉斯（scaled graph Laplacian）矩阵分别表示为：

其中为单位阵，为复合邻接矩阵，对角阵为的度矩阵（degree matrix），是的最大特征值。图卷积层通过的切比雪夫多项式（Chebyshev polynomials）参数化。记这一层的输入和输出为

则：

其中，是切比雪夫多项式第阶项，K是卷积核大小，为权重张量，为偏置项，是ELU激活函数。

时域门控卷积

如图 6c 所示，路段间参数共享的一维卷积将输入转化为张量：

其中表示一维卷积运算符。是卷积核，是卷积核的大小，是输入时序长度，是偏置项。和形状相同、通道数均为。我们使用GLU（gated linear unit）进一步引入非线性：

“”表示哈达玛积（Hadamard product）。

与STGCN的关系

时空图卷积网络（Spatio-Temporal Graph Convolutional Network，STGCN）[7]将空域图卷积层和时域门控卷积层交替地进行堆叠以同时捕捉时间和空间的依赖性。将H-STGCN的流量特征分支和邻接矩阵中的协方差项去掉，则H-STGCN退化为只有单个时空卷积块（ST-Conv block）的STGCN模型。

模型训练

数据扩充 。我们将高斯噪音叠加到流量通道中小于的值上，以提升模型的泛化能力。

优化目标 。对于本文中的多时间步预测，我们使用L1损失函数：

其中是模型的输出，为真值。

基于真实路况测试，各项指标均优于传统模型

数据集

实验数据集W3-715和E5-2907，分别对应西三环附近的715个路段和东五环附近的2907个路段（如图 7 所示）。数据集的时间跨度为2018年12月24日至2019年4月21日（其中包含的节假日被移除，共十周数据），保留的时段为每天的06:00至22:00。前八周数据作为训练集，后两周作为测试集。

                图 7  实验路网空间分布

对比模型

基线模型，包括历史均值（HA）、线性回归（LR）、GBRT、MLP、Seq2Seq、STGCN（包含单个时空卷积块）。

用于对比实验的变种模型。

• STGCN (Im)：换用复合邻接矩阵的STGCN（用于和原始的迪杰斯特拉矩阵对比。
• H-STGCN (1)：将流量特征张量V全部设成1。

评价指标

我们在三种测试集上进行模型效果的比对：

• 全测试集（如4.1节中所描述）。
• 高流量路段的拥堵时期，用C表示。
• 高流量路段的突发拥堵时期，用尾缀NRC表示。

效果比较

表 1 展示了在全测试集、测试集C、测试集NRC上不同模型的表现。评估标准包括MAE（s/m）、MAPE（%）和RMSE（s/m）。H-STGCN在各项指标上均显著优于不同的对标模型，在突发拥堵的预测方面优势尤为明显。

复合邻接矩阵 。分析表 1 可知，和STGCN相比，STGCN (Im)在W3-715数据集上有着更低的MAE、MAPE，在E5-2907数据集上有着更低的MAE、MAPE及RMSE，证明了复合邻接矩阵的有效性。图 8 以E5-2907数据集为例，对不同邻接矩阵进行可视化。图中颜色代表的值为，(a)为迪杰斯特拉矩阵，(b)为协方差矩阵，(c)为复合邻接矩阵。

图 8 E5-2970的各种邻接矩阵

未来流量特征和域转换器。如表 1 所示，和STGCN (Im)相比，H-STGCN有着稳定的更优表现，从而证实了利用未来流量数据带来的收益。由于域转换器中逐路段卷积结构的存在，H-STGCN的模型表达能力是强于STGCN (Im)的。为了消除这一影响以针对未来流量特征带来的收益做更公平的分析，我们进一步将H-STGCN与H-STGCN (1)进行对比。

在测试集C、测试集NRC上，不难发现未来流量特征在对拥堵的预测上有显著更优的表现。如图 9 所示，随着预测时间跨度的拉长，未来流量特征带来的收益会起主导作用。

 图 9 测试集NRC上效果比对

为了更加直观地对H-STGCN的原理加以剖析，我们这里展示一个突发拥堵预测的案例（如图 10 所示）。这个案例来自2018年4月16日某一高速路段。GT代表真值，HA代表历史均值，是个时间步以前对当前通行时间的预测值，是对应个时间步后的理想未来流量。17:30至18:00拥堵加剧的阶段，H-STGCN (1)提前多个时间步的预测结果和真值相比有明显的时间滞后。相比之下，H-STGCN由于有理想未来流量中的信息，甚至有能力在30min以前就对拥堵有着准确的预测。我们可以这样理解这一现象：对应的曲线代表了对15min之后交通流量的近似推算，该曲线在17:15就开始拉升了。基于导航引擎中只有当前时刻已经发起的导航行程这一事实，实际的未来流量要比理想未来流量更高。所以，的飙升预示着有较大的交通流量正在涌来，这就使H-STGCN能够在没有历史数据做参考的情况下预知未来的拥堵。

图 10 突发拥堵预测案例

模型可扩展性

模型在W3-715和E5-2097两数据集的预测时间不超过100ms。为了在实际线上应用场景中平衡推演效率和预测效果，我们将城市路网切分成最多包含几千个路段的子路网，每个子路网在线上部署一个模型。

未来将在主动交通管理方面发挥重要作用

H-STGCN已在高德驾车路线的旅行时间预测（ETA）（见图 11）中落地[9,10]，并将偏差严重的案例数量降低了15%。

H-STGCN首次以数据驱动的方式建模了用户出行意图与交通路况演化之间的相互作用，未来可以广泛的应用在主动式的交通管理领域，例如智能红绿灯调控[9]、智能道路收费系统[10]等。

图 11 ETA预测结果的展示

本文提出了一种新的用于通行时间预测的深度学习框架：混合时空图卷积网络（H-STGCN），该框架利用从导航数据中推演出的计划中交通流量提升模型效果。在真实场景数据集上进行的实验证实H-STGCN和对标的模型相比取得了更优的效果，在突发拥堵的预测上优势尤为明显。

混合时空图卷积网络提供了一种将物理知识嵌入数据驱动模型的新范式，创新性地应用了复合邻接矩阵和域转换器结构，很容易推广到一般的时空预测任务当中，未来将在智能交通管理等领域发挥重要作用。

主要参考文献：

[1] Yaguang Li, Rose Yu, Cyrus Shahabi, and Yan Liu. 2018. Diffusion convolutional recurrent neural network: Data-driven traffic forecasting.

[2] YishengLv, YanjieDuan, WenwenKang, Zhengxi Li, Fei-Yue Wang, etal. 2015. Traffic flow prediction with big data: A deep learning approach. IEEE Trans. Intelligent Transportation Systems 16, 2 (2015), 865–873.

[3] Bing Yu, Haoteng Yin, and Zhanxing Zhu. 2018. Spatio-Temporal Graph Convolutional Neural Network: A Deep Learning Framework for Traffic Forecasting. In Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI).

[4] JingruiHe, WeiShen, Phani Divakaruni, Laura Wynter, and Rick Lawrence. 2013. Improving Traffic Prediction with Tweet Semantics. In Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI). 1387–1393.

[5] Binbing Liao, Jingqing Zhang, Chao Wu, Douglas McIlwraith, Tong Chen, Shengwen Yang, Yike Guo, and Fei Wu. 2018. Deep Sequence Learning with Auxiliary Information for Traffic Prediction. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. ACM.

[6] Yaguang Li, Rose Yu, Cyrus Shahabi, and Yan Liu. 2018. Diffusion convolutional recurrent neural network: Data-driven traffic forecasting.

[7] Bing Yu, Haoteng Yin, and Zhanxing Zhu. 2018. Spatio-Temporal Graph Convolutional Neural Network: A Deep Learning Framework for Traffic Forecasting. In Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI).

[8] Moshe Ben-Akiva, Michel Bierlaire, Haris Koutsopoulos, and Rabi Mishalani. 1998. DynaMIT: A simulation-based system for traffic prediction. In DACCORD Short Term Forecasting Workshop. Delft, The Netherlands, 1–12.

[9] Wei, H., Zheng, G., Yao, H. and Li, Z., 2018. Intellilight: A reinforcement learning approach for intelligent traffic light control. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining.

[10] https://en.wikipedia.org/wiki/Congestion_pricing

温馨提示

招聘：如果你也对机器学习或运筹优化算法有着强烈的兴趣，欢迎加入阿里巴巴高德地图机器学习研发部，一起取得更多的优秀技术突破！我们是一个年轻、活跃、互助和热诚的团队，负责高德地图的共享出行及驾车导航两大业务线的效果优化工作。我们欢迎志同道合的同学们加入，一起成长，一起开拓智慧出行行业的新疆土！

岗位详情及简历投递链接：

https://alibabagroup.tupu360.com/position/detail?spm=a1zb6.8232479.detailFloor.12.6cf24a6c40pVR9&pid=5ecdfad8744a2652793921a4&pCode=G4a8gVuGzNHwbEUirrzpdg%3D%3D

也许你还想看